package com.gy.algorithm.carl.linklistexa;

import javafx.scene.control.IndexedCell;

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl.linklistexa
 * @Author: gy
 * @Date: 2024/10/26 11:24
 * @Description:
 */
public class LRUCache146 {
    public static void main(String[] args) {
        LRUCache146 lruCache = new LRUCache146(2);
        lruCache.put(2, 1); // 缓存是 {1=1}
        lruCache.put(1, 2); // 缓存是 {1=1, 2=2}
        lruCache.put(2, 3); // 缓存是 {1=1, 2=2}
        lruCache.put(4, 1); // 缓存是 {1=1, 2=2}
        System.out.println(lruCache.get(1));    // 返回 1
        System.out.println(lruCache.get(2));    // 返回 1
//        lruCache.put(1, 1); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
//        System.out.println(lruCache.get(2));    // 返回 -1 (未找到)
//        lruCache.put(4, 1); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
//         System.out.println(lruCache.get(2));    // 返回 -1 (未找到)
//         System.out.println(lruCache.get(3));    // 返回 3
//         System.out.println(lruCache.get(4));    // 返回 4

    }
    Map[] data;
    int size = 0;

    public LRUCache146(int capacity) {
        data = new Map[capacity];
    }

    public int getKeyIndex(int key){
        int index = -1;
        for (int i = 0; i < data.length; i++) {
            if(data[i] != null && key == data[i].key){
                index = i;
                break;
            }
        }
        if(index >= 0){
            return index ;
        }
        return -1;
    }

    public int get(int key) {
        int index = getKeyIndex(key);

        int res = -1;
        if(index != -1){
            res = data[index].value;
            int tmpKey = data[index].key;
            for (int i = index; i < size - 1; i++) {
                data[i] = data[i+1];
            }
            data[size - 1] = new Map(tmpKey,res);
        }

        return res;
    }

    public void put(int key, int value) {
        int index = getKeyIndex(key);

        if(index >= 0){
            data[index].value = value;
            int tmpKey = data[index].key;
            for (int i = index; i < size - 1; i++) {
                data[i] = data[i+1];
            }
            data[size - 1] = new Map(tmpKey,value);
        }else{
            // 超出缓存大小
            if(size == data.length){
                for (int i = 0; i < data.length - 1; i++) {
                    data[i] = data[i + 1];
                }
                size--;
            }
            Map map = new Map(key, value);
            data[size++] = map;
        }
    }

    class Map{
        int key;
        int value;

        public Map(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
}
